package leetcode;

/**
 * Created by Ghost on 2014/11/24 0024.
 */
public class Scramble_String {
    public boolean isScramble(String s1, String s2) {
        int len = s1.length();
        if(len!=s2.length())
            return false;
        if(s1.equals(s2))
            return true;
        int[] bools = new int[27];
        for(char a:s1.toCharArray()){
            bools[a-'a']++;
        }

        for(char b:s2.toCharArray()){
            bools[b-'a']--;
        }
        for(Integer aa:bools)
            if(aa!=0)
                return false;

        for(int i=1;i<len;i++){
            if((isScramble(s1.substring(0,i),s2.substring(0,i)) && isScramble(s1.substring(i),s2.substring(i))) ||
                    (isScramble(s1.substring(0,i),s2.substring(len-i)) && isScramble(s1.substring(i),s2.substring(0,len-i)))){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args){
        Scramble_String scramble_string = new Scramble_String();
        System.out.println(scramble_string.isScramble("great","rgate"));
    }
}
